/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 import java.lang.Integer;
 import java.lang.Math;
 
public class pathSum {
  int global_max;
  
  public int maxBranchSum(TreeNode parent) {
    if (parent == null) {
      return 0;
    }
    int leftSum = maxBranchSum(parent.left), rightSum = maxBranchSum(parent.right);
    int tmp = parent.val;
    if (leftSum > 0) tmp += leftSum;
    if (rightSum > 0) tmp += rightSum;
    global_max = Math.max(global_max, tmp);
    return Math.max(Math.max(leftSum, rightSum) + parent.val, parent.val);
  }
  
  public int maxPathSum(TreeNode root) {
    // Start typing your Java solution below
    // DO NOT write main() function 
    global_max = -9999;
    maxBranchSum(root);
    return global_max;
  }
}